#include <iostream>
using namespace std;

void print_array(int a[],int n){
	for(int i = 0;i < n;i++){
		cout << a[i] << " ";
	}
	cout <<endl;
}
void insertion_sort(int a[],int n){
	print_array(a,n);
	int c = 1;
	for(int i = 0 ;i < n;i++){
		int key = a[i];
		int j = i - 1;
		// 找到前驱
		while(j >= 0 && a[j] > key){
			a[j+1] = a[j];
			j--;
		}
		// 存放在前驱位置后面
		a[j+1] = key;
		cout << "第" << c++ << "轮"<<endl;
		print_array(a,n);
		cout <<endl;
	}
}

void test(int arr[],int n){
	for(int i = 1;i < n ;i++){
		int key = arr[i];
		int j = i - 1;
		while(j >= 0 && arr[j] > key){
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}
}
int main(){
	int a[] = {10,8,11,7,4,12,9,6,5,3};
//	insertion_sort(a,10);
	test(a,10);
	print_array(a,10);
	return 0;
}
